Optimal control problems apply to a wide range of applications such as minimum fuel landing in aerospace, and time optimal operation in manufacturing. As an example, a time optimal motion control system is widely used in positioning applications, e.g., single-axis positioning or multiple-axis positioning. A single-axis positioning motion control system includes a motion controller, a servo amplifier, and a motor. Optimal control of the motion system is generally solved in two steps to reduce a complexity of the design. The first step determines a control trajectory for the motor to control states or control constraints of the motion system, i.e., acceleration, velocity, jerk. The second step designs a controller to ensure that the motor tracks the control trajectory.
The control trajectory can also be determined to reduce the vibration induced by the motion of the motor, as well as other performance metrics, such as positioning time or energy consumption of a specific task. Due to the impact of the control trajectory on the performance of the motion control system, the determination of the control trajectory that optimizes multiple conflicting objectives is difficult.
Dynamic programming and a minimum principle are two main techniques used to solve optimal control problems. The dynamic programming reduces the optimal control problem to a set of partial differential equations; called Hamiltonian-Jacobi-Bellman equations. The minimum principle yields a set of differential equations with conditions on boundary values, i.e., a boundary value problem. The boundary value problem is a set of differential equations together with a set of boundary conditions. A solution to the boundary value problem is a solution to the differential equations which also satisfies the boundary conditions.
Solving a boundary value problem is difficult, and usually resorts to solving an initial value problem (IVP) with guessed initial conditions of the differential equations. The IVP is a set of differential equations together with specified values, called the initial condition, of the unknown function at a given point in the domain of the solution. To solve the boundary value problem using IVP, the initial values are iteratively updated until the trajectory, corresponding to the initial values, satisfies the boundary conditions.
When the operation of the system is subject to state or control constraints, a constrained optimal control problem results in multi-point boundary value problems (MBVPs). A multi-point boundary value problem is a set of ordered piecewise differential equations and corresponding boundary conditions. Typically, the boundary conditions are specified for at least three points in the domain of the solution of the MBVP. MBVPs are one of the most difficult subset of boundary value problems.
The MBVP can take the following form
                                          x            .                    =                      f            ⁡                          (                              x                ,                u                ,                t                            )                                      ,                                  ⁢                  t          ∈                      [                          0              ,              T                        ]                          ,                                  ⁢                              λ            .                    =                      g            ⁡                          (                              x                ,                λ                ,                u                ,                t                ,                μ                ,                v                            )                                      ,                                  ⁢                              h            ⁡                          (                                                x                  ⁡                                      (                                          t                      k                      -                                        )                                                  ,                                  x                  ⁡                                      (                                          t                      k                      +                                        )                                                  ,                                  λ                  ⁡                                      (                                          t                      k                      -                                        )                                                  ,                                  λ                  ⁡                                      (                                          t                      k                      +                                        )                                                  ,                                  t                  k                                ,                π                ,                μ                ,                v                            )                                =          0                ,                                  ⁢                  0          ≤          k          ≤          m                ,                                  ⁢                  u          =                                    min              u                        ⁢            H                          ,                            (        1        )            where x is a vector of state variables, λ is a vector of co-state variables, u is a vector of control variables, H is an appropriately defined Hamiltonian operator, μ, ν, π are Lagrange multipliers, m is a constant, t0 and tm represent the initial and final time respectively, and f, g, H are piecewise functions. To simplify the disclosure, x, λ, u are called state, co-state, and control variables respectively. The differential equations define how the state and costate variables evolve over time. The algebraic equations specify the value of the state and costate variables at time instants tk, and the control variable as a function of x, λ, and t. The initial time is t0=0 and the final time is tm=T.
FIG. 1 shows a conventional MBVP 110 that includes a set of ordered differential equations 120, a set of boundary conditions (BCs) 130, and a set of unknown parameters 140 to be identified. Although the parameters are independent of the definition of the MBVP, the parameters are treated as a component of the MBVP for simplification of this description. The boundary conditions are usually in the form of algebraic equations.
FIG. 2 shows an exemplary solution of the MBVP that includes the control trajectory having three segments AB1 210, B1B2 220, and B2B 230. In FIG. 2, x(t) and λ(t) represents the trajectories of state and costate variables, t1 is the time when the control trajectory switches from the first set of differential equations to the second set of differential equations, and t2 is the time when the control trajectory switches from the second set of differential equations to the third set of differential equations. Each segment of the control trajectory satisfies a different set of differential equations, i.e., the MBVP has three sets of differential equations defined over intervals [0, t1], [t1, t2], and [t2,T] respectively: the segment AB1 satisfies the first set of differential equations defined over [0, t1]; the segment B1B2 satisfies the second set of differential equations defined over [t1, t2]; and the segment B2B satisfies the third set of differential equations defined over [t2,T].
Shooting methods, including single and multiple shooting, are classic but effective methods to solve the MBVP as an initial value problem.
Single Shooting Method
FIG. 3 shows the fundamentals of the single shooting method. The curve AB 310 is a true solution of the MBVP to be searched. Since the values of state x(0) and costate λ(0) at the point A are partially unknown, information about the values of x(T) and λ(T) at the point B is used to identify the state and costate values at the point A. Given the state and costate values at the point A, the solution of the MBVP is uniquely defined because the MBVP can be solved as an initial value problem.
The method for searching the true state and costate values at the point A is as follows. First, the method estimates an initial position A′ 330 of the trajectory, implying the initial value of x(0) and λ(0). Next, the MBVP is reduced to an initial value problem whose solution, represented by the curve A′B′ 320, can be obtained by the integration of the differential equations. The solution of the initial value problem starting with A′ ends up with the final position B′ 340, which is a distance δF from the expected position B. The shooting error δF is used to update the estimate of the position of A′.
The single shooting method defines parameters at one time instant, usually the costate value at the initial time, and the boundary condition are imposed at another time instant, usually the combination of the state and costate values at the final time. As an example, the MBVP in FIG. 3 has a boundary condition, i.e., δF=0 or the point B′ coincides with B. The single shooting has properties such as a small number of parameters, easy implementation, but poor convergence, especially for the cases when the differential equations have nonlinearities or are defined over a large time interval.
The single shooting method also does not make full use of the optimal trajectory implied by the necessary conditions, and thus relies more on the quality of the initial estimate of the unknown parameters. Due to the sensitivity of the boundary conditions with respect to parameters, a solution for the single shooting method only works for a limited class of boundary value problems, for example, the linear boundary value problems, or boundary value problems defined over very short time interval. A usual observation when using a single shooting method to solve an MBVP is the singular gradient issue.
Multiple Shooting Method
Multiple shooting methods address some limitations of the single shooting method, and are generally more accurate, given the initial guess, nonlinearity in the differential equations, and large time intervals, than single shooting methods. The multiple shooting methods ameliorate the poor convergence property of the single shooting method.
FIG. 4 shows the basic idea of the multiple shooting method. The curve AB represents the solution of an MBVP, which includes three segments. The first segment satisfies the first set of differential equations, which are defined over [0, t1]. The second segment satisfies the second set of differential equations, which are defined over [t1, t2]. The third segment satisfies the third set of differential equations, which are defined over [t2, T]. To integrate the piecewise differential equations, multiple shooting methods discretizes the time interval [0,T], for an example, into N subintervals [tk,tk+1], 0≦k≦N−1, with t0=0 and tN=T.
As shown in FIG. 4, A′0, . . . , A′N−1 are the estimated values of the trajectory at time t0, . . . , tN−1, and t1, t2 are estimated switch times, i.e., the parameters are defined as values of the trajectory at points A′0, . . . , A′N−1 and switch times t1,t2. Given the initial values of x and λ at tk, 0≦k≦N−1, the differential equations are integrated over [tk,tk+1], respectively, to obtain the values of x and λ at the next time instant tk+1, and the corresponding boundary conditions are δFk=0, for 1≦k≦N−1, and δF=0. The multiple shooting method typically defines parameters and boundary conditions at the discretized time instants tk, 1≦k≦N−1 and the time instants when the control trajectory switches, e.g., t1, t2.
In contrast with the single shooting method, the multiple shooting method performs integration over a much shorter time interval [tk,tk+1], and the gradient of the boundary conditions, with respect to estimated parameters, can be approximated much accurately by sensitivity equations. The multiple shooting method has better convergence property than the single shooting methods. However, this improvement is achieved at the expenses of introducing additional parameters, which decreases the computation efficiency. The multiple shooting method can also handle a state constrained optimal control problem. However, the multiple shooting method transforms the MBVP into a large nonlinear programming problem, and the corresponding solver is computationally complex. Thus, the multiple shooting method cannot always meet a target completion time for high speed industrial applications, e.g., trajectory planning for motion control systems.
FIG. 5 shows a block diagram of a conventional iterative procedure for solving the MBVP for given parameters and boundary conditions. The parameters are initially estimated 510 and based on the initial estimate of parameters, the MBVP is solved 520 as an initial value problem of differential equations. The solution is tested 530 against the boundary conditions. The parameters are updated 550 if the boundary conditions are not satisfied, otherwise, the method outputs 540 the control trajectory.